/*********************************************************************************************************
 *  ------------------------------------------------------------------------------------------------------
 *  file description
 *  ------------------------------------------------------------------------------------------------------
 *         \file  map.c
 *        \brief  This is a general-purpose C language map module, with common value structure
 *       \author  Lamdonn
 *        \email  Lamdonn@163.com
 *      \version  1.1.0
 *      \license  GPL2
 *    \copyright  Copyright (C) 2023 Lamdonn.
 ********************************************************************************************************/
#include "vlib.h"
#include <stdlib.h>
#include <string.h>

#define IDENT                           (7)

/* map node type define */
typedef struct NODE
{
    struct NODE *parent;                /* parent node */
    struct NODE *left;                  /* left node */
    struct NODE *right;                 /* right node */
    int color;                          /* red black color */
    void *value;                        /* address of value */
    map_key_t key;                      /* key of item */
} NODE, *node_t;

/* map node color */
#define MAP_COLOR_BLACK                 (0)
#define MAP_COLOR_RED                   (1)

/* map child */
#define MAP_CHILD_LEFT                  (0)
#define MAP_CHILD_RIGHT                 (1)

map_key_t *map_nil_key(void *map)
{
    return &(((node_t)(((map_t)map)->nil))->key);
}

/** __fun_map_create
 *  \brief create map
 *  \param[in] value_size: size of map value
 *  \param[in] ktpye: entity or pointer @ref MAP_KEY_TYPE
 *  \param[in] ksize: size of key
 *  \param[in] trans: the parameter transform to key
 *  \return map handler or NULL: fail
 */
map_t __fun_map_create(int value_size, int ktpye, int ksize, void* trans)
{
    map_t map = NULL;

    /* alloc map space */
    map = (map_t)vlib_malloc(sizeof(MAP));
    if (map == NULL)
    {
        return NULL;
    }

    /* alloc nil node space */
    map->nil = vlib_malloc(sizeof(NODE));
    if (map->nil == NULL)
    {
        vlib_free(map);
        return NULL;
    }

    /* alloc nil value space */
    ((node_t)(map->nil))->value = vlib_malloc(value_size);
    if (((node_t)(map->nil))->value == NULL)
    {
        vlib_free(map->nil);
        vlib_free(map);
        return NULL;
    }

    if (ktpye == MAP_KEY_TYPE_ENTITY) /* alloc entity key space */
    {
        ((node_t)(map->nil))->key.address = vlib_malloc(ksize);
        if (((node_t)(map->nil))->key.address == NULL)
        {
            vlib_free(((node_t)(map->nil))->value);
            vlib_free(map->nil);
            vlib_free(map);
            return NULL;
        }
    }
    else if (ktpye == MAP_KEY_TYPE_POINTER)
    {

    }

    ((node_t)(map->nil))->color = MAP_COLOR_BLACK;
    map->parent.ident = IDENT;
    map->parent.base = map->nil;
    map->parent.size = 0;
    map->parent.dsize = value_size;
    map->ktpye = ktpye;
    map->trans = (map_key_trans_t)trans;

    return map;
}

/** recursion_delete_node
 *  \brief recursively delete all nodes under the node
 *  \param[in] map: map handler
 *  \param[in] node: map node
 *  \return none
 */
static void recursion_delete_node(map_t map, node_t node)
{
    if (node == map->nil)
    {
        return;
    }

    /* recursive call */
    recursion_delete_node(map, node->left);
    recursion_delete_node(map, node->right);

    /* release */
    vlib_free(node->value);
    vlib_free(node);
}

/** __fun_map_delete
 *  \brief delete map
 *  \param[in] map: map handler
 *  \return none
 */
void __fun_map_delete(map_t map)
{
    if (!map) return;

    map_clear(map);
    if (map->ktpye == MAP_KEY_TYPE_ENTITY)
    {
        vlib_free(((node_t)(map->nil))->key.address);
    }
    vlib_free(((node_t)(map->nil))->value);
    vlib_free(map->nil);
    vlib_free(map);
}

/** key_compare
 *  \brief compare two keys
 *  \param[in] key0: key0
 *  \param[in] key1: key1
 *  \return none
 */
static int key_compare(map_key_t key0, map_key_t key1)
{
    unsigned char *add0 = (unsigned char *)key0.address;
    unsigned char *add1 = (unsigned char *)key1.address;

    while (key0.size && key1.size)
    {
        key0.size--;
        key1.size--;

        if (*add0 < *add1)
        {
            return -1;
        }
        else if (*add0 > *add1)
        {
            return 1;
        }
        
        add0++;
        add1++;
    }

    if (key0.size < key1.size)
    {
        return -1;
    }
    else if (key0.size > key1.size)
    {
        return 1;
    }

    return 0;
}

/** map_find_node
 *  \brief find node by key
 *  \param[in] map: map handler
 *  \param[in] key: key
 *  \return node or nil: fail
 */
static node_t map_find_node(map_t map, map_key_t key)
{
    node_t node = map->parent.base;

    /* binary search */
    while (node != map->nil)
    {
        if (key_compare(key, node->key) < 0)
        {
            node = node->left;
        }
        else if (key_compare(key, node->key) > 0)
        {
            node = node->right;
        }
        else
        {
            return node;
        }    
    }

    return map->nil;
}

/** map_left_rotate
 *  \brief tree left rotation
 *  \param[in] map: map handler
 *  \param[in] x: node to be rotated
 *  \return none
 */
static void map_left_rotate(map_t map, node_t x) 
{
    node_t y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right

    x->right = y->left; // 1 1
    if (y->left != map->nil) // 1 2
    {
        y->left->parent = x;
    }

    y->parent = x->parent; // 1 3
    if (x->parent == map->nil) // 1 4
    {
        map->parent.base = y;
    }
    else if (x == x->parent->left)
    {
        x->parent->left = y;
    }
    else
    {
        x->parent->right = y;
    }

    y->left = x; //1 5
    x->parent = y; //1 6
}

/** map_right_rotate
 *  \brief tree right rotation
 *  \param[in] map: map handler
 *  \param[in] x: node to be rotated
 *  \return none
 */
static void map_right_rotate(map_t map, node_t y) 
{
    node_t x = y->left;

    y->left = x->right;
    if (x->right != map->nil)
    {
        x->right->parent = y;
    }

    x->parent = y->parent;
    if (y->parent == map->nil)
    {
        map->parent.base = x;
    }
    else if (y == y->parent->right)
    {
        y->parent->right = x;
    }
    else
    {
        y->parent->left = x;
    }

    x->right = y;
    y->parent = x;
}

/** map_insert_fixup
 *  \brief maintaining the properties of red-black tree after inserting node
 *  \param[in] map: map handler
 *  \param[in] z: node to be insert
 *  \return none
 */
static void map_insert_fixup(map_t map, node_t z) 
{
    node_t y = NULL;

    while (z->parent->color == MAP_COLOR_RED) // z ---> MAP_COLOR_RED
    {
        if (z->parent == z->parent->parent->left)
        {
            y = z->parent->parent->right;

            /* the uncle node of the inserted node is red */
            if (y->color == MAP_COLOR_RED)
            {
                z->parent->color = MAP_COLOR_BLACK;
                y->color = MAP_COLOR_BLACK;
                z->parent->parent->color = MAP_COLOR_RED;

                z = z->parent->parent; //z --> MAP_COLOR_RED
            }
            else
            {
                /* the uncle node is black, and the inserted node is the right child of the parent node */
                if (z == z->parent->right)
                {
                    z = z->parent;
                    map_left_rotate(map, z);
                }

                z->parent->color = MAP_COLOR_BLACK;
                z->parent->parent->color = MAP_COLOR_RED;
                map_right_rotate(map, z->parent->parent);
            }
        }
        else
        {
            /* the uncle node of the inserted node is red */
            y = z->parent->parent->left;
            if (y->color == MAP_COLOR_RED)
            {
                z->parent->color = MAP_COLOR_BLACK;
                y->color = MAP_COLOR_BLACK;
                z->parent->parent->color = MAP_COLOR_RED;

                z = z->parent->parent; //z --> MAP_COLOR_RED
            }
            else
            {
                /* the uncle node is black, and the inserted node is the left child of the parent node */
                if (z == z->parent->left)
                {
                    z = z->parent;
                    map_right_rotate(map, z);
                }
        
                z->parent->color = MAP_COLOR_BLACK;
                z->parent->parent->color = MAP_COLOR_RED;
                map_left_rotate(map, z->parent->parent);
            }
        }
    }

    ((node_t)(map->parent.base))->color = MAP_COLOR_BLACK;
}

/** map_insert_node
 *  \brief insert node into map
 *  \param[in] map: map handler
 *  \param[in] z: node to be insert
 *  \return none
 */
static void map_insert_node(map_t map, node_t z)
{
    /* use fast and slow pointers to traverse the red black map. the slow pointer is the father of the fast pointer */
    node_t y = map->nil;
    node_t x = map->parent.base;

    while (x != map->nil)
    {
        y = x;
        
        if (key_compare(z->key, x->key) < 0)
        {
            x = x->left;
        }
        else if (key_compare(z->key, x->key) > 0)
        {
            x = x->right;
        }
        else /* A node with key z ->key already exists, and it returns directly */
        {
            return;
        }
    }

    z->parent = y;
    /* the original map is empty, and the newly inserted node is the root node */
    if (y == map->nil)
    {
        map->parent.base = z;
    }
    else if (key_compare(z->key, y->key) < 0)
    {
        y->left = z;
    }
    else
    {
        y->right = z;
    }

    z->left = map->nil;
    z->right = map->nil;
    z->color = MAP_COLOR_RED; /* the newly inserted node is red by default */

    /* maintain the properties of map */
    map_insert_fixup(map, z);
}

/** __fun_map_insert
 *  \brief insert value into the map according to the key
 *  \param[in] map: map handler
 *  \param[in] key: key
 *  \param[in] value: address of map value
 *  \return 1: success or 0: fail
 */
int __fun_map_insert(map_t map, map_key_t key, void* value)
{
    node_t parent_node = NULL;
    node_t new_node = NULL;
    int child = 0;

    if (!map) return 0;
    
    /* alloc new node */
    new_node = (node_t)vlib_malloc(sizeof(NODE));
    if (new_node == NULL)
    {
        return 0;
    }

    /* alloc value space */
    new_node->value = vlib_malloc(map->parent.dsize);
    if (new_node->value == NULL)
    {
        vlib_free(new_node);
        return 0;
    }

    /* alloc key space */
    new_node->key.address = vlib_malloc(key.size);
    if (new_node->key.address == NULL)
    {
        vlib_free(new_node->value);
        vlib_free(new_node);
        return 0;
    }
    memcpy(new_node->key.address, key.address, key.size);
    new_node->key.size = key.size;

    if (value != NULL) memcpy(new_node->value, value, map->parent.dsize);

    map_insert_node(map, new_node);

    map->parent.size++;

    return 1;
}

/** map_erase_fixup
 *  \brief maintaining the properties of red-black tree after erase node
 *  \param[in] map: map handler
 *  \param[in] x: node that needs erase
 *  \return none
 */
static void map_erase_fixup(map_t map, node_t x) 
{
    node_t w = NULL;

    while ((x != map->parent.base) && (x->color == MAP_COLOR_BLACK))
    {
        /* this if is mirrored with the corresponding else */
        if (x == x->parent->left)
        {
            /* find the sibling node */
            w = x->parent->right;
            
            /* 1. sibling node is red */
            if (w->color == MAP_COLOR_RED)
            {
                w->color = MAP_COLOR_BLACK;
                x->parent->color = MAP_COLOR_RED;
                
                /* parent node left rotate */
                map_left_rotate(map, x->parent);
                
                w = x->parent->right;
            }
            
            /* 2. sibling node is black, and siling's childs are black */
            if ((w->left->color == MAP_COLOR_BLACK) && (w->right->color == MAP_COLOR_BLACK))
            {
                w->color = MAP_COLOR_RED;
                x = x->parent;
            }
            else
            {
                /* 3. sibling node is black, left child is red and right child is black */
                if (w->right->color == MAP_COLOR_BLACK)
                {
                    w->left->color = MAP_COLOR_BLACK;
                    w->color = MAP_COLOR_RED;
                    
                    /* sibling node right rotate */
                    map_right_rotate(map, w);

                    w = x->parent->right;
                }
                
                /* 4. siling node is black, and siling childs are red */
                w->color = x->parent->color;
                x->parent->color = MAP_COLOR_BLACK;
                w->right->color = MAP_COLOR_BLACK;
                
                /* parent node left rotate */
                map_left_rotate(map, x->parent);
                
                x = map->parent.base;
            }

        }
        else
        {
            w = x->parent->left;
            if (w->color == MAP_COLOR_RED)
            {
                w->color = MAP_COLOR_BLACK;
                x->parent->color = MAP_COLOR_RED;

                map_right_rotate(map, x->parent);

                w = x->parent->left;
            }

            if ((w->left->color == MAP_COLOR_BLACK) && (w->right->color == MAP_COLOR_BLACK))
            {
                w->color = MAP_COLOR_RED;
                x = x->parent;
            }
            else
            {
                if (w->left->color == MAP_COLOR_BLACK)
                {
                    w->right->color = MAP_COLOR_BLACK;
                    w->color = MAP_COLOR_RED;

                    map_left_rotate(map, w);

                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = MAP_COLOR_BLACK;
                w->left->color = MAP_COLOR_BLACK;

                map_right_rotate(map, x->parent);

                x = map->parent.base;
            }
        }
    }
    
    x->color = MAP_COLOR_BLACK;
}

/** map_mini
 *  \brief find the minimum node in the right subtree
 *  \param[in] map: map handler
 *  \param[in] x: base node
 *  \return minimum node handler
 */
static node_t map_mini(map_t map, node_t x)
{
    if (x == map->nil) return x;
    while (x->left != map->nil)
    {
        x = x->left;
    }

    return x;
}

/** map_maxi
 *  \brief find the maximum node in the right subtree
 *  \param[in] map: map handler
 *  \param[in] x: base node
 *  \return minimum node handler
 */
static node_t map_maxi(map_t map, node_t x)
{
    if (x == map->nil) return x;
    while (x->right != map->nil)
    {
        x = x->right;
    }

    return x;
}

/** map_successor
 *  \brief get the succeed node
 *  \param[in] map: map handler
 *  \param[in] x: base node
 *  \return succeed node handler
 */
static node_t map_successor(map_t map, node_t x) 
{
    node_t y = x->parent;
    
    if (x->right != map->nil)
    {
        return map_mini(map, x->right);
    }

    while ((y != map->nil) && (x == y->right))
    {
        x = y;
        y = y->parent;
    }

    return y;
}

/** key_swap
 *  \brief swap two keys
 *  \param[in] key0: address of key0
 *  \param[in] key1: address of key1
 *  \return none
 */
static void key_swap(map_key_t *key0, map_key_t *key1)
{
    map_key_t temp;

    temp = *key0;
    *key0 = *key1;
    *key1 = temp;
}

/** value_swap
 *  \brief swap two value
 *  \param[in] *value0: address of value0's pointer
 *  \param[in] *value1: address of value1's pointer
 *  \return none
 */
static void value_swap(void **value0, void **value1)
{
    void *temp;

    temp = *value0;
    *value0 = *value1;
    *value1 = temp;
}

/** map_erase_node
 *  \brief erase node from map
 *  \param[in] map: map handler
 *  \param[in] z: base node
 *  \return node to be released
 */
static node_t map_erase_node(map_t map, node_t z) 
{
    node_t y = map->nil;
    node_t x = map->nil;

    /* the child node has no children or only one child. it directly points to this node */
    if ((z->left == map->nil) || (z->right == map->nil))
    {
        y = z;
    }
    else
    {
        y = map_successor(map, z);
    }

    /* if the son node has an only child, the only child directly inherits its parent's position */
    if (y->left != map->nil)
    {
        x = y->left;
    }
    else if (y->right != map->nil)
    {
        x = y->right;
    }

    x->parent = y->parent;
    if (y->parent == map->nil)
    {
        map->parent.base = x;
    }
    else if (y == y->parent->left)
    {
        y->parent->left = x;
    }
    else
    {
        y->parent->right = x;
    }
    
    /* if y is the smallest node of the right subtree, place y at z, and then delete the original z */
    if (y != z)
    {
        key_swap(&z->key, &y->key);
        value_swap(&z->value, &y->value);
    }

    /* if the deleted node is black, maintain the property of map */
    if (y->color == MAP_COLOR_BLACK)
    {
        map_erase_fixup(map, x);
    }

    return y;
}

/** __fun_map_erase
 *  \brief erase value from map according to key
 *  \param[in] map: map handler
 *  \param[in] key: key
 *  \return 1: success or 0: fail
 */
int __fun_map_erase(map_t map, map_key_t key)
{
    node_t node = NULL;
    node_t cur = NULL;

    if (!map) return 0;

    node = map_find_node(map, key);
    if (node == map->nil)
    {
        return 0;
    }

    cur = map_erase_node(map, node);
    vlib_free(cur->key.address);
    vlib_free(cur->value);
    vlib_free(cur);

    map->parent.size--;

    return 1;
}

/** map_clear
 *  \brief clear all nodes under the map
 *  \param[in] map: map handler
 *  \return none
 */
void map_clear(map_t map)
{
    if (!map) return;

    recursion_delete_node(map, map->parent.base);
    map->parent.base = map->nil;
    map->parent.size = 0;
}

/** map_size
 *  \brief get the size of map
 *  \param[in] map: map handler
 *  \return size of map
 */
int map_size(map_t map)
{
    if (!map) return 0;
    return map->parent.size;
}

/** __fun_map_find
 *  \brief find key from map
 *  \param[in] map: map handler
 *  \param[in] key: key
 *  \return 1: success or 0: fail
 */
int __fun_map_find(map_t map, map_key_t key)
{
    if (!map) return 0;
    return map_find_node(map, key)==map->nil?0:1;
}

void* map_data(map_t map, map_key_t key)
{
    if (!map) return 0;
    return map_find_node(map, key)->value;
}

/** recursion_traverse
 *  \brief recursively traverse value in map
 *  \param[in] map: map handler
 *  \param[in] node: node to be traversed
 *  \param[in] traverse: traverse function
 *  \return none
 */
static void recursion_traverse(map_t map, node_t node, map_traverse_t traverse)
{
    if (node == map->nil)
    {
        return;
    }

    recursion_traverse(map, node->left, traverse);
    traverse(node->key, node->value);
    recursion_traverse(map, node->right, traverse);
}

/** 
 *  \brief swap two map
 *  \param[in] map: map handler
 *  \param[in] swap: map handler of swap
 *  \return none
 */
void map_swap(map_t map, map_t swap)
{
    MAP temp;

    if (!map) return;
    if (!swap) return;

    temp = *map;
    *map = *swap;
    *swap = temp;
}

/** map_traverse
 *  \brief traverse value in map
 *  \param[in] map: map handler
 *  \param[in] traverse: traverse function
 *  \return none
 */
void map_traverse(map_t map, map_traverse_t traverse)
{
    if (!map) return;
    if (!traverse) return;
    recursion_traverse(map, map->parent.base, traverse);
}

/** map_error
 *  \brief error return value
 *  \param[in] map: map handler
 *  \return error pointer
 */
void* map_error(map_t map)
{
    if (!map) return NULL;
    return ((node_t)(map->nil))->value;
}

/** map_node_next
 *  \brief map next node
 *  \param[in] map: map handler
 *  \param[in] cur: current node
 *  \return next node
 */
static node_t map_node_next(map_t map, node_t cur)
{
    if (cur->right != map->nil)
    {
        cur = cur->right;
        cur = map_mini(map, cur);
    }
    else  
    {
        if (cur == cur->parent->left) /* current node is left child */
        {
            cur = cur->parent;
        }
        else /* current node is right child */
        {
            cur = cur->parent->parent;
        }
    }

    return cur;
}

/** map_node_prev
 *  \brief map previous node
 *  \param[in] map: map handler
 *  \param[in] cur: current node
 *  \return previous node
 */
static node_t map_node_prev(map_t map, node_t cur)
{
    if (cur->left != map->nil)
    {
        cur = cur->left;
        cur = map_maxi(map, cur);
    }
    else  
    {
        if (cur == cur->parent->right) /* current node is right child */
        {
            cur = cur->parent;
        }
        else /* current node is left child */
        {
            cur = cur->parent->parent;
        }
    }

    return cur;
}

void* map_iterator_begin(vobject_t object)
{
    node_t node = NULL;
    if (!object) return NULL;
    node = map_mini((map_t)object, ((map_t)object)->parent.base);
    return (void *)node;
}

void* map_iterator_end(vobject_t object)
{
    node_t node = NULL;
    if (!object) return NULL;
    node = map_maxi((map_t)object, ((map_t)object)->parent.base);
    return (void *)node;
}

void* map_iterator_move(vobject_t object, void *node, int step)
{
    node_t n = node;
    if (step > 0)
    {
        while (step--) n = map_node_next((map_t)object, n);
    }
    else if (step < 0) 
    {
        while (step++) n = map_node_prev((map_t)object, n);
    }
    return (void *)n;
}

void map_iterator_nfs(void *node, void **first, void **second)
{
    if (!node) return;
    if (first) *first = &(((node_t)node)->key);
    if (second) *second = ((node_t)node)->value;
}

void map_algorithm_swap(vobject_t object, void *node0, void *node1)
{
    map_t map = (map_t)object;
    node_t n0 = node0, n1 = node1;
    void *temp;
    temp = n0->value;
    n0->value = n1->value;
    n1->value = temp;
}
